package graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * expecting O(k*e), k<=2
 * 
 * BellmanFord faster implementation
 * 
 * @author yinzichen
 * 
 */
public class SPFA {
	public int[] spfa(ArrayList<ArrayList<Integer[]>> adj, int vertexNum,
			int edgeNum, int source) {
		int[] d = new int[vertexNum];
		boolean[] visit = new boolean[vertexNum];
		int[] num = new int[vertexNum];
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i = 0; i < vertexNum; ++i)
			d[i] = Integer.MAX_VALUE;
		d[source] = 0;
		visit[source] = true;
		q.add(source);
		num[source]++;
		while (!q.isEmpty()) {
			int u = q.poll();
			visit[u] = false;
			for (Integer[] v : adj.get(u)) {
				if (d[v[0]] > d[u] + d[v[1]]) {
					d[v[0]] = d[u] + d[v[1]];
					if (!visit[v[0]]) {
						visit[v[0]] = true;
						q.add(v[0]);
						num[v[0]]++;
						if (num[v[0]] > edgeNum) {
							return null;
						}
					}
				}
			}
		}
		return d;
	}
}
